/*
 * @Author: szx
 * @Date: 2022-04-16 15:39:56
 * @LastEditTime: 2022-04-16 16:30:49
 * @Description:
 * @FilePath: \leetcode\剑指offerII\065\065.js
 */

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function (words) {
    const trie = {};
    for (let word of words) {
        let node = trie;
        for (let i = word.length - 1; i >= 0; i--) {
            const w = word[i];
            if (!node[w]) {
                node[w] = {};
            }
            node = node[w];
        }
    }
    let res = 0;
    const dfs = (root, depth) => {
        const values = Object.values(root);
        if (values.length == 0) {
            res += depth;
            return;
        }
        for (let i of values) {
            dfs(i, depth + 1);
        }
    };
    dfs(trie, 1);
    return res;
};

var minimumLengthEncoding = function (words) {
    const set = new Set();
    for (let word of words) {
        for (let i = word.length - 1; i > 0; i--) {
            if (set.has(word.substring(i, word.length))) {
                set.delete(word.substring(i, word.length));
            }
        }
    }
    let res = 0;
    for (let s of set) res += s.length + 1;
    return res;
};
